package leetcode.editor.cn;
//给定一个正整数数组 nums 和一个整数 target 。 
//
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 
//
// 
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 
// 
//
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,1,1], target = 3
//输出：5
//解释：一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], target = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 20 
// 0 <= nums[i] <= 1000 
// 0 <= sum(nums[i]) <= 1000 
// -1000 <= target <= 1000 
// 
//
// 
//
// 
// 注意：本题与主站 494 题相同： https://leetcode-cn.com/problems/target-sum/ 
//
// Related Topics 数组 动态规划 回溯 👍 31 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_102 {

    /**
     * 滚动数组优化
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target){
        int sum = Arrays.stream(nums).sum();
        if(sum - target < 0 || ((sum-target) & 1) !=0) return 0;
        //dp[j]:nums中前i个元素可以组成和为j的组合个数(i从0开始)
        int[] dp = new int[(sum-target)/2+1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = dp.length-1; j >=0; j--){
                if(j >= nums[i]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[dp.length-1];
    }

    public int findTargetSumWays2(int[] nums, int target){
        int sum = Arrays.stream(nums).sum();
        if(sum - target < 0 || ((sum-target) & 1) !=0) return 0;
        //dp[i][j]:nums中前i个元素可以组成和为j的组合个数(i从1开始)
        int[][] dp = new int[nums.length+1][(sum-target)/2+1];
        dp[0][0] = 1;
        for(int i = 1; i <= nums.length; i++){
            for(int j = 0; j <= (sum-target)/2; j++){
                if(j >= nums[i-1]){
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[nums.length][(sum-target)/2];
    }

    int target;
    int result = 0;
    public int findTargetSumWays1(int[] nums, int target) {
        this.target  = target;
        dfs(nums, 0, 0);
        return result;
    }

    private void dfs(int[] nums, int index, int sum){
        if(index == nums.length){
            if(sum == target){
                result++;
            }
            return;
        }
        if(index < nums.length){
            dfs(nums, index+1, sum+nums[index]);
            dfs(nums, index+1, sum-nums[index]);
            //不能用++index,否则sum+nums[index]中的index会提前加1
            //也不能用index++,否则index永远不变
//            dfs(nums, ++index, sum+nums[index]);
//            dfs(nums, ++index, sum-nums[index]);
        }
    }

    public static void main(String[] args) {
        int targetSumWays = new SolutionOffer2_102().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3);
        System.out.println(targetSumWays);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
